package tplenguajes.grafo;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

import org.antlr.runtime.tree.CommonTree;

import tplenguajes.TParser;

public class AFND<T> extends FiniteAutomata<T>
{
	public AFND(CommonTree ast, Set<T> alphabet)
	{
		super(alphabet);
		
		AutomataState end = new AutomataState();
		addVertex(end);
		end.setAsFinal();
		
		int token = ast.getToken().getType();
		
		if ( token == TParser.OR )
		{
			FiniteAutomata<T> left = new AFND<T>((CommonTree)ast.getChild(0),alphabet);
			FiniteAutomata<T> right = new AFND<T>((CommonTree)ast.getChild(1),alphabet);
			
			this.addAutomata(left);
			this.addAutomata(right);
			
			addLambdaTransition(this.getRoot(), left.getRoot());
			addLambdaTransition(this.getRoot(), right.getRoot());
			
			for ( AutomataState leftEnd : left.getFinalStates() )
				addLambdaTransition(leftEnd, end);
			
			for ( AutomataState rightEnd : right.getFinalStates() )
				addLambdaTransition(rightEnd, end);
			
			unsetFinals(left);
			unsetFinals(right);
		}
		else if ( token == TParser.CL )
		{
			FiniteAutomata<T> expression = new AFND<T>((CommonTree)ast.getChild(0),alphabet);
			
			this.addAutomata(expression);
			
			addLambdaTransition(this.getRoot(), end);
			addLambdaTransition(this.getRoot(), expression.getRoot());
			
			for ( AutomataState exprEnd : expression.getFinalStates() )
			{
				addLambdaTransition(exprEnd, end);
				addLambdaTransition(exprEnd, expression.getRoot());
			}
			
			unsetFinals(expression);
		}
		else if ( token == TParser.CLP )
		{
			FiniteAutomata<T> expression = new AFND<T>((CommonTree)ast.getChild(0),alphabet);
			
			this.addAutomata(expression);
			
			addLambdaTransition(this.getRoot(), expression.getRoot());
			
			for ( AutomataState exprEnd : expression.getFinalStates() )
			{
				addLambdaTransition(exprEnd, end);
				addLambdaTransition(exprEnd, expression.getRoot());
			}
			
			unsetFinals(expression);
		}
		else if ( token == TParser.OPC )
		{
			FiniteAutomata<T> expression = new AFND<T>((CommonTree)ast.getChild(0),alphabet);
			
			this.addAutomata(expression);
			
			addLambdaTransition(this.getRoot(), end);
			addLambdaTransition(this.getRoot(), expression.getRoot());
			
			for ( AutomataState exprEnd : expression.getFinalStates() )
				addLambdaTransition(exprEnd, end);
			
			unsetFinals(expression);
		}
		else if ( token == TParser.ERCONCAT && ast.getChildCount() == 2 )
		{
			FiniteAutomata<T> left = new AFND<T>((CommonTree)ast.getChild(0),alphabet);
			FiniteAutomata<T> right = new AFND<T>((CommonTree)ast.getChild(1),alphabet);
			
			this.addAutomata(left);
			this.addAutomata(right);
			
			addLambdaTransition(this.getRoot(), left.getRoot());
			
			for ( AutomataState leftEnd : left.getFinalStates() )
				addLambdaTransition(leftEnd, right.getRoot());
			
			for ( AutomataState rightEnd : right.getFinalStates() )
				addLambdaTransition(rightEnd, end);
			
			unsetFinals(left);
				unsetFinals(right);
		}
		else if ( token == TParser.ER || ( token == TParser.ERCONCAT && ast.getChildCount() == 1 ) )
		{
			FiniteAutomata<T> expression = new AFND<T>((CommonTree)ast.getChild(0),alphabet);
			
			this.addAutomata(expression);
			
			addLambdaTransition(this.getRoot(), expression.getRoot());
			
			for ( AutomataState exprEnd : expression.getFinalStates() )
				addLambdaTransition(exprEnd, end);
			
			unsetFinals(expression);
		}
		else if ( token == TParser.ANY )
		{
			for ( T transition : getAlphabet() )
				addStateTransition(this.getRoot(), end, (String)transition);
		}
		else if ( token == TParser.CAR )
		{
			String transition = ast.toString();
			
			addStateTransition(this.getRoot(), end, transition);
		}
		else
			System.err.println("Unhandled token "+token+" building AFND from tree");
	}
	
	public Set<AutomataState> getEpsilonClosure(Set<AutomataState> initialClosure)
	{
		Set<AutomataState> closure = new HashSet<AutomataState>(initialClosure);
		Stack<AutomataState> stack = new Stack<AutomataState>();
		
		for (AutomataState subState : initialClosure)
			stack.push(subState);
		
		while (!stack.isEmpty())
		{
			AutomataState subState = stack.pop();
			
			for ( Edge<AutomataState> e : getOutgoingEdges(subState) )
				if ( e instanceof LambdaTransition )
					if ( !closure.contains(e.getTarget()) )
					{
						closure.add(e.getTarget());
						stack.push(e.getTarget());
					}
		}
		
		return closure;
	}
	
	
	public Set<AutomataState> getTargets(Set<AutomataState> sources, T transition)
	{
		Set<AutomataState> targets = new HashSet<AutomataState>();
		
		for ( AutomataState state : sources )
			for ( Edge<AutomataState> edge : getOutgoingEdges(state) )
				if ( !(edge instanceof LambdaTransition) )
					if ( getLabel(edge).equals(transition) )
						targets.add(edge.getTarget());
		
		return targets;
	}
	
	
	public boolean isFinalClosure(Set<AutomataState> closure)
	{
		for ( AutomataState state : closure )
			if ( state.isFinal() )
				return true;
		
		return false;
	}
	
	private void addAutomata(FiniteAutomata<T> automata)
	{
		for (AutomataState v : automata.getVertices() )
			addVertex(v);
		
		for (Edge<AutomataState> e : automata.getEdges() )
			addEdge(automata.getEdgeSource(e), automata.getEdgeTarget(e), e);
	}
	
	private void unsetFinals(FiniteAutomata<T> automata)
	{
		for (AutomataState v : automata.getVertices() )
			v.unsetAsFinal();
	}
	
	private boolean addLambdaTransition(AutomataState src, AutomataState dst)
	{
		return this.addEdge(src, dst, new LambdaTransition(src,dst));
	}
	
	
	private boolean addStateTransition(AutomataState src, AutomataState dst, String transition)
	{
		return this.addEdge(src, dst, new StateTransition<String>(src, dst, transition));
	}
	
}
